区间dp

一.概念

对于一段区间求最优解,且该区间可以分为几个小区间的最优解合并(最优子结构)。

二.基本思路

阅读全文 »

伯努利数

伯努利数是一个用于解决 nn 次方和的数列。

它的递归定义公式如下:

i=0n(n+1i)Bi=[n=0]        (1.1)\sum_{i=0}^n \binom {n+1} i B_i=[n=0] ~~~~~~~~ (1.1)

阅读全文 »

CF113D Museum

fi,jf_{i,j}:两人分别在房间 i,ji,j 的概率。初始状态 fa,b=1f_{a,b}=1

fi,j=pipjfi,j+(i,u)E(j,v)E1pudegu1pvdegvfu,vf_{i,j}=p_ip_jf_{i,j}+\sum_{(i,u) \in E}\sum_{(j,v) \in E} \frac{1-p_u}{\deg_u} \frac{1-p_v}{\deg_v}f_{u,v}

阅读全文 »

P3211 [HNOI2011]XOR和路径

异或的期望不能直接算,对每一位单独考虑。

f[u][0/1]f[u][0/1]:节点 uu 的第 ii 位为 0/10/1 的概率。

注意经过节点 uu 的概率不一定为 11 ,所以 f[u][0]+f[u][1]f[u][0]+f[u][1] 的值不一定为 11

阅读全文 »

CF575A Fibonotci

考试的时候写了3.5h , 考后又写了2h 才过掉。

每次修改只会影响两个矩阵,可以暴力计算。

我们知道矩阵乘法有结合律,那么两次修改之间的矩阵可以快速求出乘积。

阅读全文 »